package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis22 {
    private List<String> list = new ArrayList<>();
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;

        helper("", 0, 0);
        return list;
    }
    private void helper(String s, int left, int right){
        //终止条件
        if(left==n && right==n){
            list.add(s);
            return;
        }
        //剪枝
        if(left>n || left<right){return;}
        //递归
        helper(s+"(", left+1, right);
        helper(s+")", left, right+1);
    }
}
